import java.util.Arrays;
import java.util.HashMap;

public class CheckInclusion {

    public static void main(String[] args) {
        CheckInclusion checkInclusion = new CheckInclusion();
        System.out.println(checkInclusion.checkInclusion("adc", "dcda"));
    }

    public boolean checkInclusion1(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        HashMap<Character, Integer> maps = new HashMap<>();
        for (int i = 0; i < n; i++) {
            maps.put(chars1[i], maps.getOrDefault(chars1[i], 0) + 1);
        }
        HashMap<Character, Integer> temp = new HashMap<>(maps);
        for (int i = 0; i <= m - n; i++) {
            for (int j = i; j < i + n; j++) {
                if (temp.containsKey(chars2[j])) {
                    if (temp.get(chars2[j]) > 1) {
                        temp.put(chars2[j], temp.get(chars2[j]) - 1);
                    } else {
                        temp.remove(chars2[j]);
                    }
                } else {
                    temp = new HashMap<>(maps);
                    break;
                }
                if (temp.isEmpty()) return true;
            }
        }
        return false;
    }

    public boolean checkInclusion2(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int target = 0;
        HashMap<Character, Integer> maps = new HashMap<>();
        for (int i = 0; i < n; i++) {
            maps.put(chars1[i], maps.getOrDefault(chars1[i], 0) + 1);
        }
        HashMap<Character, Integer> temp = new HashMap<>(maps);
        for (int i = 0; i < m; i++) {
            if (temp.containsKey(chars2[i])) {
                if (temp.get(chars2[i]) > 0) {
                    temp.put(chars2[i], temp.get(chars2[i]) - 1);
                    if (temp.get(chars2[i]) == 0) target++;
                } else {
                    temp.put(chars2[i], maps.get(chars2[i]) - 1);
                    if (temp.get(chars2[i]) != 0) target--;
                }
            } else {
                temp = new HashMap<>(maps);
                target = 0;
            }
            if (target == n) return true;
        }
        return false;
    }

    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        if (n > m) return false;
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int[] nums1 = new int[26];
        int[] nums2 = new int[26];
        for (int i = 0; i < n; i++) {
            ++nums1[chars1[i] - 'a'];
            ++nums2[chars2[i] - 'a'];
        }
        if (Arrays.equals(nums1, nums2)) return true;
        for (int i = n; i < m; i++) {
            ++nums2[chars2[i] - 'a'];
            --nums2[chars2[i - n] - 'a'];
            if (Arrays.equals(nums1, nums2)) return true;
        }
        return false;
    }
}
